COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	6.2 Three image formats: Video, CRE and FEV.
C00006 00003	KINDS OF CRE NODES.
C00011 00004	CRE LINK AND DATUM NAMES.
C00014 00005	CRE RINGS, TREES, LISTS AND ARRAYS.
C00017 00006	
C00021 ENDMK
C⊗;
6.2 Three image formats: Video, CRE and FEV.

DATA STRUCTURE: BASICS.

	The two generic data structures of CRE  are arrays and nodes;
there are  five kinds of arrays  and eight kinds of  nodes.

  The node
structures is implemented as seven word  fixed sized
blocks. The data structure in CRE  represents a  sequence in
time of video  intensity contour maps.   Such contour  maps are  like
topographical elevation  contour maps, in  that no two  contour lines
should  ever cross and in  that all the contour  lines should close.
Consequently,  the loops  of  contours  enclose  regions;  and  these
regions  overlap  in  a  nested  fashion forming  a  tree  like  data
structure.

	As  the  general  examples  of  contoured  images  on page  5
illustrate, a notion that is  emphatically not in CRE,  is that  of a
schematic line drawing.   Although the CRE output can  be viewed as a
collection of lines  on a display  screen,  people  expecting a  line
drawing  rendition   of  the   given  television   picture  will   be
disappointed.    A CRE  picture  is a  simple  transformation  of the
photometry,   geometry  and topology  of  the original  video  image;
whereas  the typical  line  drawing  from a  human  illustrator is  a
representation  of the scene without  photometric information. On the
other  hand,   the  work  of  an  artist  such as  Peter  Max;  or  a
paint-by-the-numbers grid  does resembly CRE output.   This is not an
idle coincidance  but rather  a  consequence of  whether or  not  the
artist is trying to represent photometric data by quantum lines.

	The explanation of  CRE node structures will be  presented in
three  parts: first,   the  several  kinds of  nodes will  be briefly
explained; second,   the  sub  structures such  as rings,  trees  and
lists  will be  discribed; and  third,   the node  formats and  their
contents  will be  explained in  detail.
KINDS OF CRE NODES.

	The are  eight kinds of  CRE nodes: Vector,   Arc,   Polygon,
Shape,  Image, Level, Film and Empty.

1. At  the very top of all the structure is  the film node,  the film
node is unique  and serves as  an OBLIST from  which all other  nodes
may  be reached.   The  film node  embodies the  idea of  a piece  of
celluloid  film or  a length  of magnetic  video tape.   A film  is a
sequence of images  taken by the same  camera of the same  scene with
only a small amount of action between images.

2. An  image node represents the  familiar two dimensional  idea of a
photograph or an oil  painting or to be  exact a digital video  image
of 216 rows by 288  columns of numbers ranging from 0 for  dark to 63
for bright.   The image is formed by a  thin lens and is projected on
a flat image  plane. The idea  of an image  is so  common that it  is
easy to overlook the wonder of  sun light scattering off of surfaces,
refracting  thru a lens, and forming a  complex pattern called a real
image.

3.  Below the image node are the intensity  contour levels. A contour
level is a binary image  that results from thresholding a gray scaled
image. So an image  is composed of  levels, and in  turn, a level  is
composed of polygons.

4.   A  Polygon node  represents the  idea  of a  contour loop  which
always  closes upon  itself and  does not cross  itself or  any other
contour. Contour loops are approximated by a ring of  vectors; hence,
the term "polygon".  The contour polygons always have  at least three
sides and are simply connected.

5. Shape nodes contain data about one or two  polygons. The data in a
shape node  is not a positive representation  of the notion of shape;
but is  rather the parameters  of allignment  and normalization  that
must be compensated before shapes can be compared.

6. Vector nodes contain the locus  of an image vertex; however  since
vectors always  belong to a  polygon and  always have two  neighbors;
their  counterclockwise  neighbor is  considered  to  determine their
vector direction.

7.  Arc  nodes are  vectors that  are made by  the polygon  smoothing
routine; one  arc typically replace  several vectors. When  both arcs
and vectors  are being discussed; vectors are strictly horizontal and
vertical, whereas arcs may point in any direction.

8.   Empty  nodes are  an artifact  of the  fixed  node size  dynamic
storage  allocation mechanism  used  in CRE.   Entities  are  made by
taking empty nodes  from an  AVAIL list  and entities  are killed  by
returning  their  node  to  the  AVAIL  list;  there  is  no  garbage
collector,  but there is a space compactor.
CRE LINK AND DATUM NAMES.
	
	Nodes  contain either  numerical data  or  pointers to  other
nodes;  such  node  pointers are  actual  machine  addresses and  are
called links. The positions within a node where a link is  stored are
named and  are reserved for particular  uses. In the table  below the
11  link names  and 13 datum  names are  introduced.   The link names
will always appear capitalized.

	11 LINK NAMES:

		CW	clockwise
		CCW	counter clockwise
		DAD	parent of node up a tree structure.
		SON	descendent of a node down a tree structure.
		ENDO	Greek for inside, polygon within.
		EXO	Greek for outside, surrounding polygon.
		ALT	alternate.
		NGON	negative polygon.
		PGON	positive polygon.
		NTIME	negative in real time, into the past.
		PTIME	positive in real time, into the future.

	13 DATUM NAMES:

	   Boolean datums.

		type		type of node bits.
		reloc		rellocation of node bits.

	   Fixed point datums.

		row		row of image locus.
		col		column of image locus.
		cntrst		contrast of an edge, vector and arc.
		ncnt		number count, various uses.

	   Floating point datums.

		zdepth		z depth from camera lens center.
		perm		length of perimeter.
		area		area in pixel units.
		mxx		moment of inertia about X axis.
		myy		moment of inertia about Y axis.
		mzz		moment of inertia about Z axis.
		pxy		product of inertia with respect
				to the X and Y axes.
CRE RINGS, TREES, LISTS AND ARRAYS.

	CRE inputs an image into an array  called TVBUF; it makes the
node structures, some  of which are temporary; and it outputs a final
version  of  the  structure  representing  a  film  of   images.  The
temporary structures  are relevant to understanding  the process; but
only  the  final  structure is  relevant  to using  CRE  output.   In
summary, the important structures are:

	FOUR RINGS.
		1. Image ring of the film.
		2. Level ring of an image.
		3. Polygon ring of a level.
		4. Vector ring of a polygon.

	TWO TREES.
		1. The tree of rings.
		2. The tree of nested polygons.

	TWO LISTS.
		1. Time line lists.
		2. The empty node list.

	TEMPORARY STRUCTURES.
		1. Arc rings of polygons.
		2. Fusion shape rings of levels.

	FIVE ARRAYS.
		1. TVBUF - 216 rows, 288 columns of  6 bit bytes.
		2. PAC   - 216 rows, 288 columns of  1 bit bytes.
		3. VSEG  - 216 rows, 289 columns of  1 bit bytes.
		4. HSEG  - 217 rows, 288 columns of  1 bit bytes.
		5. SKY   - 216 rows, 289 columns of 18 bit bytes.

	There is one  film node.  The film  is composed of a  ring of
images.   Each image is composed of a ring  of levels.  Each level is
composed of a ring  of polygons. Each polygon  is composed of a  ring
of vectors.  The ring structures  are implemented with the four links
named  DAD, SON,   CW and  CCW.  The  rings are headless  only in the
sense that all the elements of a ring are brothers;  a pointer to the
head of a ring is stored  in the DAD link of each element. The DAD of
the film node is  NIL; and NIL  is an 18-bit zero.  The final SON  of
all vector nodes  is also NIL. The DAD  and SON links form a  tree of
rings.

	Besides the  tree  of rings,   there  is the  tree of  nested
polygons.   The  nested  polygon tree  is implemented  with  the four
links named ENDO, EXO,  NGON and  PGON.  The EXO of a polygon  points
at its  surronding polygon. The  ENDO of a  polygon points at  one of
the  polygons that may be enclaved within  the given polygon; and the
NGON and PGON links  form a ring of  polygons that have the  same EXO
polygon.

	The time line  lists run thru arc and polygon  nodes.  In the
simple  case,    the  time  line  links  of  a  polygon  point  to  a
corresponding polygon  in the  image previous  (NTIME) or  subsequent
(PTIME)  of the  current polygon. The  correspondence being  that the
time polygon  is  exactly  the  same intensity  at  nearly  the  same
location, orientation, and size as the  given polygon. In the case of
polygon  fusion, the  time line link  of a  polygon points  to a time
polygon of which the  given polygon becomes a  part.  In the  case of
polygon fission, the  time line link of a polygon  points to only one
the pieces into which the given polygon splits.

	The  time  line   links  of   an  arc  vector   point  to   a
corresponding arc vector in  the image previous or subsequent  of the
current  arc vector. The  polygons of arc  vectors mated  in time are
also mated in time; because  after polygon time line links have  been
made, one polygon  is temporarily translated, rotated  and dilated so
as  to have the same  lamina inertia tensor as its  mate; that is the
locus of  the arc  vectors of  one polygon  are temporarily  altered;
then  the corresponding  arc vectors  are found  and their  time line
linkages are made.

	The empty node list is maintained in the CCW link  positions;
the last empty  node contains a  zero link. All nodes  are explicitly
made  from  and killed  to the  empty  node list  by  the subroutines
MKNODE and KLNODE.

	The arc ring of  a polygon is just like a  vector ring except
that  the pointer to  it is  stored in the  ALT link of  the polygon,
while the polygon has both a ring of vectors and a ring of arcs.

	The  fusion shape ring of a intensity  level runs thru the CW
and CCW links  of shape nodes and  is pointed at  by the ALT link  of
the level.  Fusion shape  nodes are the shapes generated to represent
pairs of polygons unmated in time.